package main

import "fmt"

func leftBound(nums []int, target int) int {
	if len(nums) == 0 {
		return -1
	}
	left := 0
	right := len(nums) - 1
	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] >= target {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	if left < 0 || left >= len(nums) || nums[left] != target {
		return -1
	}
	return left
}

func rightBound(nums []int, target int) int {
	if len(nums) == 0 {
		return -1
	}
	left := 0
	right := len(nums) - 1
	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] <= target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	if right < 0 || right >= len(nums) || nums[right] != target {
		return -1
	}
	return right
}

func searchRange(nums []int, target int) []int {
	return []int{
		leftBound(nums, target),
		rightBound(nums, target),
	}
}

func main() {
	ret := searchRange([]int{1}, 0)
	fmt.Printf("%#v\n", ret)
	ret = searchRange([]int{5, 7, 7, 8, 8, 10}, 5)
	fmt.Printf("%#v\n", ret)
	ret = searchRange([]int{}, 0)
	fmt.Printf("%#v\n", ret)
}
